Authentication of users in a network allows a pair of users who wish to communicate to prove their identities to each other. There are many variations of authentication protocols that are discussed in the literature. Some require the use of a shared secret, such as a secret digital key or a secret mathematical function, that is applied to a suitable parameter or parameters; others use public-key types of protocols. This invention is concerned primarily with authentication protocols using shared secrets, although it can be easily adapted for use in public-key systems.
With respect to the prior art, U.S. Pat. No. 4,890,323, "Data Communication Systems and Methods", issued on Dec. 26, 1989 to Beker, describes a file and sender authentication method in which an encrypted check-sum is computed on the contents of a message using a first private key. This check-sum is issued as a "challenge" to a user who computes a result using a second private key. The result is appended to the response as an authentication code before return transmission. A recipient of the response equipped with the same first and second crytographic keys can therefore check both the contents of the message and the identity of the sender by computing an expected authentication code from the received response and comparing it with the code received.
U.S. Pat. No. 4,919,545, "Distributed Security Procedure for Intelligent Networks", which issued on Apr. 24, 1990 to C. Yu, discloses a file authentication method. An execution node transmits a capability and a signature to an invocation node. The capability includes an identifier of and access rights to a file. The signature is formed at the execution node by encryption of the capability with a key that is unique to the invocation node and is stored only in the execution node. A request for access to the file is transmitted with the capability and the signature from the invocation node to the execution node. At the execution node, the request is authenticated by encryption of the capability with the encryption key that is associated with the invocation node. Access to the file is authorized only when the signature generated by the execution node matches the signature received from the invocation node.
U.S. Pat. No. 4,193,131, entitled "Crytographic Verification of Operational Keys Used in Communication Networks", issued on Mar. 11, 1980 to R. Lennon et. al. This patent discloses an encryption key distribution and user authentication method using a shared private key. A first station encrypts a first verification number using the key to provide first station ciphertext for transmission to the second station. At the second station, the first station ciphertext is further encrypted using the key to provide second station ciphertext for transmission back to the first station. The first station reencrypts the first verification cipertext and compares it the received second station ciphertext to verify that the second station is the source of the second station ciphertext. This authentication is possible only if the operational keys of the two stations are identical.
U.S. Pat. No. 4,386,233, "Cryptographic Key Notarization Methods and Apparatus", issued on May 31, 1983 to M. E. Smid et. al., also discloses a key distribution system and user authentication method in which cryptographic keys are notarized by encrypting the keys using a notarizing key derived from identifiers associated with the users in question and an interchange key accessible only to authorized users of the cryptographic function. The identity of a user of the cryptographic function is authenticated as a condition to access to an interchange key. This authentication is accomplished by comparing a password designation supplied by the user with a prestored version of the password which has been notarized by having been encrypted with the cryptographic function using a notarizing cryptographic key derived from the identifier of the corresponding authorized user and an interchange key.
U.S. Pat. No. 4,218,738, "Method for Authenticating the Identity of a User of an Information System", issued to S. M. Matyas et. al. on Aug. 19, 1980 discloses yet another method of attempting to authenticate users in a network. A user verification number is a function of the user's identity, a separately entered password associated with the user, and a stored test pattern. The test pattern for a user is generated under physical security of a central computer using a variation of a host computer master key.
U.S. Pat. No. 4,549,075, "Method of Certifying the Origin of at Least One Item of Information Stored in the Memory of a First Electronic Device and Transmitted to a Second Electronic Device, and System for Carrying Out the Method", issued to Charles Saada Oct. 22, 1985. This patent discloses a shared secret type of authentication protocol, which is said to overcome certain problems in the prior art authentication method summarized therein. In this prior art method, a user B authenticates a user A. Both A and B share an item of information I, a secret S and a function f( ). To begin an authentication, A sends I to B. B responds with a random number, a nonce, Nb. Both A and B compute f(I,Nb,S). A sends its computed response to B and B compares this response with its calculation. It is said that A can authenticate B in a similar manner. Saada does not point out that this prior art protocol can be easily broken in a general network environment. Rather, Saada attempts to solve the problem posed by the prior art method when A and B do not share an item of information I, but rather have their own individual items of information Ia and Ib. Saada applies the summarized prior art method to this new scenario and concludes that resulting protocol can easily be broken.
Thus, Saada's invention is to allow the users to authenticate each other when each has different information units Ia and Ib. Again, A and B share a function f( ) and a secret S. A has an item of information Ia; B has an item of information Ib. A sends Ia and a nonce Na to B. B returns item Ib and another nonce Nb to A. A calculates R1=f(Na,S,p(Ia,Ib) and K1=f(Nb,S,p(Ia,Ib)) and sends K1 to B. p( ) is a symmetric function known both to A and B. The symmetry means that p(Ia,Ib)=p(Ib,Ia). B calculates K2=f(Na,S,p(Ib,Ia)) and R2=f(Nb,S,p(Ib,Ia)) and sends K2 to A. A compares K2 with its result R1 to authenticate B and B compares K1 with its result R2 to authenticate A. It is said that this protocol insures that A and B are part of the same group, because of the secret S, and that A and B are who they say they are, because the items Ia and Ib are authenticated one-to-the-other via the symmetric function p( ). It is seen that Saada's algorithm requires a minimum of four message flows. It is the fourth flow that prevents this method from being broken by methods that are described briefly below.
In yet another known authentication method, user A first sends to user B a challenge Na in the form of a nonce (message 1). B returns an encrypted value of the nonce using a private shared key to perform the encryption, plus a second nonce Nb in clear text (message 2). A then returns an encrypted value of the second nonce to B (message 3) who verifies that this response was properly encrypted with the shared key. This protocol requires three messages. However, as will be shown, this protocol can also be easily broken.
As seen by the above summarized art, existing authentication methods use various forms of shared secrets and encryption of data by the users, using a shared key, to assure that the users are who they say they are. However, the existing methods suffer from a number of problems. In theory, each user authenticates the other because the proper encryptions and/or decryptions cannot be generated by a user that does not know the shared secret. In practice however, these authentication methods either require too many message flows, or too many encryption or decryption operations, or are subject to a variety of successful attacks.
Using the last mentioned authentication method for example, in a first successful type of attack, an intruder X, pretending to be A, initiates the attack by sending the first challenge Na to B (message 1). B returns the encrypted value of the first challenge E(Na), plus the second challenge Nb (message 2). X, who does not know the secret key, obtains the correct encryption of Nb by initiating another connection (called a reference connection throughout the description) with the real A, or some other user C who knows the key, and transmits Nb as the first challenge of the reference connection. A, or C, returns E(Nb) to X as a response. X then sends E(Nb) to B as the answer to the second challenge of the initial attack connection.
In a second type of attack as another example, X intercepts the first message containing Na from A intended for B. X, pretending to be B, initiates a reference connection with A (or C) and sends Na in message 1 of the reference connection. A (or C) responds with E(Na) and a second nonce Nb. X then terminates the reference connection and sends E(Na) in the second message to A on the attack connection.
There are a number of variations of the above initiate and intercept attacks. In all of these attacks, however, the intruder X, not knowing the secret shared by legitimate users, gleans information from other connections and uses this information to derive the necessary responses to challenges offered by the attacked user. The connections from which the gleaned information is obtained may or may not be with the attacked user. As far as can be determined, all of the known prior art methods that involve only three message flows can be broken, or are inefficient and unnecessarily complex to use or evaluate. Other known methods involving more than three flows may or may not be secure. However, even for the secure methods, the increased number of message flows that are required can place a heavy traffic burden on a network. This additional burden is otherwise unproductive and limits the capacity of the network from the users point of view.
Thus, there exists a clear need to establish an authentication protocol and method that is immune from otherwise successful attacks by intruders that have no knowledge of the authentication secret. Furthermore, it is important in any practical implementation of a protocol that the number of message flows required to carry out the authentication be kept as small as possible, preferably three, at the risk of otherwise overburdening the network.